package sharewithus.analyzer.utils;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;


/**
 * 三叉词典树
 * 
 * @author terry
 * 
 * @param <T>
 */
public class TernaryTrie<T>{

	private TSTNode<T> root;

	public void add(String key, T val) {
		TSTNode<T> currentNode = getOrCreateNode(key);
		currentNode.data = val;
	}

	public T find(String key) {
		TSTNode<T> currentNode = getNode(key);
		if (currentNode == null) {
			return null;
		}
		return currentNode.data;
	}

	public TSTNode<T> getNode(String key) {
		int len = key.length();
		TSTNode<T> currentNode = root; // 匹配过程中的当前节点的位置
		int charIndex = 0; // 当前要比较的字符在查询词中的位置
		char currentChar = key.charAt(charIndex); // 当前要比较的字符
		int charComp;
		while (true) {
			if (currentNode == null) {// 没找到
				return null;
			}
			// 比较查询词中的字符与节点中的字符
			charComp = currentChar - currentNode.splitChar;
			if (charComp == 0) {// 查询词中的字符与节点中的字符相等
				charIndex++;
				if (charIndex == len) {// 找到了
					// System.out.println("find node:"+currentNode.nodeValue);
					return currentNode;
				}
				currentChar = key.charAt(charIndex);
				currentNode = currentNode.mid;
			} else if (charComp < 0) {// 查询词中的字符小于节点中的字符
				currentNode = currentNode.left;
			} else {// 查询词中的字符大于节点中的字符
				currentNode = currentNode.right;
			}
		}
	}

	// 创建一个词相关的节点并返回对应的叶结点
	public TSTNode<T> getOrCreateNode(String key) {
		if (key == null) {
			throw new NullPointerException(
					"attempt to get or create node with null key");
		}
		if ("".equals(key)) {
			throw new IllegalArgumentException(
					"attempt to get or create node with key of zero length");
		}
		int charIndex = 0; // 当前要比较的字符在查询词中的位置
		char currentChar = key.charAt(charIndex); // 当前要比较的字符
		if (root == null) {
			root = new TSTNode<T>(currentChar);
		}
		TSTNode<T> currentNode = root;
		while (true) {
			// 比较词的当前字符与节点的当前字符
			int compa = currentChar - currentNode.splitChar;
			if (compa == 0) { // 词中的字符与节点中的字符相等
				charIndex++;
				if (charIndex == key.length())
					return currentNode;

				currentChar = key.charAt(charIndex);
				if (currentNode.mid == null)
					currentNode.mid = new TSTNode<T>(currentChar);

				currentNode = currentNode.mid; // 向下找
			} else if (compa < 0) { // 词中的字符小于节点中的字符
				if (currentNode.left == null)
					currentNode.left = new TSTNode<T>(currentChar);

				currentNode = currentNode.left; // 向左找
			} else { // 词中的字符大于节点中的字符
				if (currentNode.right == null)
					currentNode.right = new TSTNode<T>(currentChar);

				currentNode = currentNode.right; // 向右找
			}
		}
	}

	/**
	 * 匹配英文
	 * 
	 * @param start 开始位置
	 * @param sentence 文本
	 * @return 结束位置
	 */
	public int matchEnglish(int start, String sentence) {
		int i = start;
		int count = sentence.length();
		String sd = "ＱＷＥＲＴＹＵＩＯＰＡＳＤＦＧＨＪＫＬＺＸＣＶＢＮＭ号";
		while (i < count) {
			char c = sentence.charAt(i);
			if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
				++i;
			} else if (sd.indexOf(c) > -1) {
				++i;
			} else {
				break;
			}
		}
		return i;
	}

	/**
	 * 匹配数字
	 * 
	 * @param start 开始位置
	 * @param sentence 文本
	 * @return 结束位置
	 */
	public int matchNum(int start, String sentence) {
		int i = start;
		int count = sentence.length();
		while (i < count) {
			char c = sentence.charAt(i);
			if ((c >= '0' && c <= '9') || (c >= '０' && c <= '９') || c == '-'
					|| c == '－') {
				++i;
			} else {
				break;
			}
		}
		if (i > start && i < count) {
			char end = sentence.charAt(i);
			if ('号' == end || '#' == end || '＃' == end) {
				i++;
			}
		}
		return i;
	}

	public List<MatchRet<T>> matchAll(String key, int offset, T enData,
			T numData) {
		List<MatchRet<T>> matchRets = new LinkedList<MatchRet<T>>();
		if (key == null || root == null || "".equals(key)
				|| offset >= key.length()) {
			return matchRets;
		}

		int ret = offset;

		ret = matchNum(offset, key);
		if (ret > offset) {
			MatchRet<T> matchRet = new MatchRet<T>(ret, key.substring(offset,
					ret), numData);
			matchRets.add(matchRet);
		}

		int retEnglishNum = matchEnglish(offset, key);
		if (retEnglishNum > ret) {
			ret = retEnglishNum;
			MatchRet<T> matchRet = new MatchRet<T>(ret, key.substring(offset,
					ret), enData);
			matchRets.add(matchRet);
		}

		TSTNode<T> currentNode = root;
		int charIndex = offset;
		while (true) {
			if (currentNode == null) {
				return matchRets;
			}
			int charComp = key.charAt(charIndex) - currentNode.splitChar;

			if (charComp == 0) {
				charIndex++;

				if (currentNode.data != null) {
					ret = charIndex;
					MatchRet<T> matchRet = new MatchRet<T>(ret, key.substring(
							offset, ret), currentNode.data);
					matchRets.add(matchRet);
				}
				if (charIndex == key.length()) {
					return matchRets;
				}
				currentNode = currentNode.mid;
			} else if (charComp < 0) {
				currentNode = currentNode.left;
			} else {
				currentNode = currentNode.right;
			}
		}
	}

	public void print() {
		TSTNode<T> currentNode = root;

		/* 用于存放节点数据的队列 */
		Deque<TSTNode<T>> queueNode = new ArrayDeque<TSTNode<T>>();
		queueNode.addFirst(currentNode);

		/* 广度优先遍历所有树节点，将其加入至数组中 */
		while (!queueNode.isEmpty()) {
			/* 取出队列第一个节点 */
			currentNode = queueNode.pollFirst();

			/* 写入splitChar */
			System.out.println(currentNode.splitChar);

			/* 处理左子节点 */
			if (currentNode.left != null) {
				queueNode.addLast(currentNode.left);
				System.out
						.println("left node is " + currentNode.left.splitChar);
			} else {
				System.out.println("left node is null");
			}

			/* 处理中间子节点 */
			if (currentNode.mid != null) {
				queueNode.addLast(currentNode.mid);
				System.out.println("middle node is "
						+ currentNode.mid.splitChar);
			} else {
				System.out.println("middle node is null");
			}

			/* 处理右子节点 */
			if (currentNode.right != null) {
				queueNode.addLast(currentNode.right);
				System.out.println("right node is "
						+ currentNode.right.splitChar);
			} else {
				System.out.println("right node is null");
			}
		}

	}

	public ArrayList<TSTNode<T>> getBrothers() {
		ArrayList<TSTNode<T>> ret = new ArrayList<TSTNode<T>>();
		TSTNode<T> currentNode = root;

		/* 用于存放节点数据的队列 */
		Deque<TSTNode<T>> queueNode = new ArrayDeque<TSTNode<T>>();
		queueNode.addFirst(currentNode);

		/* 广度优先遍历所有树节点，将其加入至数组中 */
		while (!queueNode.isEmpty()) {
			/* 取出队列第一个节点 */
			currentNode = queueNode.pollFirst();

			/* 写入splitChar */
			// System.out.println(currentNode.splitChar);
			ret.add(currentNode);

			/* 处理左子节点 */
			if (currentNode.left != null) {
				queueNode.addLast(currentNode.left);
				// System.out.println("left node is "+currentNode.left.splitChar);
			} else {
				// System.out.println("left node is null");
			}

			/* 处理右子节点 */
			if (currentNode.right != null) {
				queueNode.addLast(currentNode.right);
				// System.out.println("right node is "+currentNode.right.splitChar);
			} else {
				// System.out.println("right node is null");
			}
		}
		return ret;
	}

}
